package code1_100.code20_30;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 *
 */
public class _21mergeTwoLists {

    public static void main(String[] args) {
        //ListNode l1 = new ListNode(1,new ListNode(2,new ListNode(4)));
        //ListNode l2 = new ListNode(1,new ListNode(3,new ListNode(4)));
        ListNode l1 = null;
        ListNode l2 = new ListNode(1,new ListNode(3,new ListNode(4)));
        ListNode outp = mergeTwoLists(l1, l2);
        while (outp!=null){
            System.out.println(outp.val);
            outp = outp.next;
        }
    }

    /**
     * 一次通过
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
     * 内存消耗：37.6 MB, 在所有 Java 提交中击败了95.54% 的用户
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode l1Root = l1,l2Root = l2;
        ListNode root = new ListNode();
        ListNode temp = root;
        while (l1Root != null && l2Root != null) {
            ListNode sumNode = new ListNode();
            if (l1Root.val < l2Root.val) {
                sumNode.val = l1Root.val;
                l1Root = l1Root.next;
            }else {
                sumNode.val = l2Root.val;
                l2Root = l2Root.next;
            }
            temp.next = sumNode;
            temp = sumNode;
        }
        if(l1Root==null){
            temp.next = l2Root;
        }
        if(l2Root==null){
            temp.next = l1Root;
        }
        return root.next;
    }

}

